Data Structure
Q21.
Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from [1....n] (2) If A[i] = x then stop else Goto 1; Assuming that x is present A, What is the expected number of comparisons made by the algorithm before it terminates?Q22.
Consider the following declaration of a two-dimensional array in C : Char a[100][100] Assuming that the main memory is byte-addressable and that array is stored starting form memory address 0, the address of a [40] [50] isQ23.
An n \times n array v is defined as follows: v\left[i,j\right] = i - j for all i, j, i \leq n, 1 \leq j \leq n The sum of the elements of the array v isQ24.
Suppose you are given an array s[1....n] and a procedure reverse (s, i, j) which reverses the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where 1 \leqslant k \leqslant n: reverse (s, 1, k); reverse (s, k+1, n); reverse (s, 1, n);Q25.
Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case isQ26.
Let A be a two dimensional array declared as follows: A: array [1 ... 10] [1 ... 15] of integer; Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element A[i][j]?Q27.
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n \times n, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)^{th} element of the lower triangular matrix in this new representation is:Q28.
The average number of key comparisons required for a successful search for sequential search on n items isQ30.
With reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "Get all records with a search key greater than or equal to 7 and less than 15" is ____________.